package com.demo.java.OD51_100.OD66;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【单词接龙】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145612235
 */
public class OdMain {
    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);
            int k = Integer.parseInt(s.nextLine()); // 目标单词的位置
            int N = Integer.parseInt(s.nextLine()); // 单词的总数

            // 如果 N 不符合预期，输出错误
            if (N <= 1 || N >= 20) {
                System.out.println("data error");
                return;
            }

            ArrayList<String> wordList = new ArrayList<>();
            // 将单词添加到列表
            for (int i = 0; i < N; ++i) {
                wordList.add(s.nextLine());
            }

            StringBuilder sb = new StringBuilder();
            sb.append(wordList.get(k)); // 将第 k 个单词作为起始单词
            wordList.remove(k); // 移除已使用的单词

            // 排序，按单词长度降序，如果长度相同按字典顺序
            wordList.sort((word1, word2) -> {
                int length1 = word1.length();
                int length2 = word2.length();
                if (length1 != length2) {
                    return length2 - length1; // 降序排列
                } else {
                    return word1.compareTo(word2); // 字典序排列
                }
            });

            // 拼接符合条件的单词
            int length;
            do {
                length = sb.length();
                char lastChar = sb.charAt(sb.length() - 1); // 获取最后一个字母
                for (int i = 0; i < wordList.size(); ++i) {
                    String value = wordList.get(i);
                    if (value.charAt(0) == lastChar) { // 判断是否符合首尾字符相同的规则
                        sb.append(value); // 拼接
                        wordList.remove(i); // 移除已拼接的单词
                        break;
                    }
                }
            } while (length != sb.length()); // 如果拼接长度没有变化，说明没有符合条件的单词

            // 输出最终拼接的字符串
            System.out.println(sb);
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }

}